<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        /* 
        题目描述：
            给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
            请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
            假设每一种面额的硬币有无限个。 
            例： 
                输入：amount = 5, coins = [1, 2, 5]
                输出：4
                解释：有四种方式可以凑成总金额：
                5=5
                5=2+2+1
                5=2+1+1+1
                5=1+1+1+1+1      
        */
       /* 
       错误思路：
       f(n)表示拼n元有几种，求f(n) = sum(f(n - coins[i])),就和青蛙跳荷叶的思路是一样的，
        但是这里忽略了一个问题，青蛙跳荷叶是求排列数，112和121是两种方案；本题目是求组合数，112和121是同一种方案。
        所以状态方程有问题
       */
       function Charge(coins,amount){
           // 初始化状态
           let f = new Array(amount + 1).fill(0)
           f[0] = 1
           for(let i = 1; i <= amount; i++){
               for(let j = 0; j < coins.length; j++){
                   if(i >= coins[j]){
                       f[i] += f[i - coins[j]]
                   }
               }
           }
           return f[amount]
       }
      /* 
        正确思路：将最终值放在外层循环，可选值放在内层遍历出来是排列数，
                将可选值放在外层，最终值放在内层遍历出来是组合数，先遍历可选值，这样计算出来的结果是不会有重复的情况
            
      */
      function Charge2(coins,amount){
           // 初始化状态
           let f = new Array(amount + 1).fill(0)
           f[0] = 1
           for(let i = 0; i <= coins.length; i++){
               for(let j = 1; j <= amount ; j++){
                   if(j >= coins[i]){
                       f[j] += f[j - coins[i]]
                   }
               }
           }
           return f[amount]
       }

       let amount = 5
       let coins = [1, 2, 5]
       console.log(Charge(coins,amount))
       console.log(Charge2(coins,amount))
    </script>
</body>
</html>